#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
    ElementType Data;
    PtrToNode   Next;
};
typedef PtrToNode List;

List Read(); /* 细节在此不表 */
void Print( List L ); /* 细节在此不表；空链表将输出NULL */

List Merge( List L1, List L2 );

void prtL( List L1 ){
	if ( L1->Next == NULL)printf("NULL\n");
	while( L1->Next ){
		L1=L1->Next;
		printf("%d\n",L1->Data);
	}
}
int main()
{
    //List L1, L2, L;
    //L1 = Read();
    //L2 = Read();
    //L = Merge(L1, L2);
    //Print(L);
    //Print(L1);
    //Print(L2);

	struct Node a[]={
				{.Data=1,.Next=&a[1]},
				{.Data=2,.Next=&a[2]},
				{.Data=3,.Next=&a[3]},
				{.Data=4,.Next=&a[4]},
				{.Data=5,.Next=&a[5]},
				{.Data=6,.Next=NULL}
			};

	struct Node b[]={
				{.Data=1,.Next=&b[1]},
				{.Data=2,.Next=&b[2]},
				{.Data=3,.Next=&b[3]},
				{.Data=4,.Next=&b[4]},
				{.Data=5,.Next=&b[5]},
				{.Data=6,.Next=NULL}
			};
	struct Node tmp1,tmp2;
	struct Node *p1,*p2;
	p1=&tmp1,p2=&tmp2;
	p1->Next=&a[0];
	p2->Next=&b[0];


	
	printf("Merge List\n");
	List ret=Merge(p1,p2);
	prtL( ret );

	printf("L1 List\n");
	prtL( p1 );
	printf("L2 List\n");
	prtL( p2 );
    return 0;
}

/* 你的代码将被嵌在这里 */

List Merge( List L1, List L2 ){
	List ret,tmp,l1,l2;
	ret=tmp=malloc(sizeof(struct Node));
	l1=L1;
	l2=L2;
	L1=L1->Next;
	L2=L2->Next;
	while( L1 && L2 ){
		if( L1->Data > L2->Data ){
			tmp->Next=L2;
			L2=L2->Next;
			tmp=tmp->Next;
		}
		//else if ( L1->Data == L2->Data ){
		//	tmp->Next=L1;
		//	L1=L1->Next;
		//	L2=L2->Next;
		//	tmp=tmp->Next;
		//}
		else{
			tmp->Next=L1;
			L1=L1->Next;
			tmp=tmp->Next;
		}
	}
	while( L1 ){
		tmp->Next=L1;
		L1=L1->Next;
		tmp=tmp->Next;
	}
	while( L2 ){
		tmp->Next=L2;
		L2=L2->Next;
		tmp=tmp->Next;
	}
	l1->Next=NULL;
	l2->Next=NULL;
	return ret;
}
